# 反转链表II： https://leetcode-cn.com/problems/reverse-linked-list-ii/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 自己的写法
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        """
            这道题和反转链表 一样，我的思路是 
            1. 记录 left 前一个位置节点， 记录right 后一个位置节点。代码实现：
                leftPre = head
                while leftPre.next != left:
                    leftPre = leftPre.next
                这里存在一个问题： 当head需要反转时，无法求出来正确的leftPre， 为了使逻辑统一。必须设立首元结点。
            2. 将left 到 right 反转
            3. 重新指向，反转后的链表，构成新链表

            注意点在于。 给的是 int 类型下标 left ，right 而非节点
        """
        dumpy = ListNode(0, head)
        # 1. 找leftPre
        leftPre = dumpy
        index = 0
        while index != left - 1:
            leftPre = leftPre.next
            index += 1

        leftNode = leftPre.next

        # 2. 找到 rightNext: 同样需要注意， rightNext 为 None, 不过不管为何，不影响拼接
        rightNext = leftPre
        while index != right:
            rightNext = rightNext.next
            index += 1
        rightNext = rightNext.next

        # 3. 反转: 使用迭代法
        p, pre = leftNode, None
        while p != rightNext:
            cur = p
            p = p.next
            cur.next = pre
            pre = cur
        
        # 4. 拼接
        leftPre.next = pre 
        # 是不是None，都不影响拼接
        leftNode.next = rightNext

        # 5. 重新指向head
        head = dumpy.next

        return head


# 可以优化代码
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        """
            优化代码
        """
        dumpy = ListNode(0, head)
        leftPre = leftNode = rightNext = dumpy
        
        index = 0
        # 可以合并找 leftPre， rightNext的代码
        while index < right + 1:
            if index == left - 1:
                leftPre = rightNext
                leftNode = leftPre.next
    
            index += 1
            rightNext = rightNext.next

        # 3. 反转: 使用迭代法
        p, pre = leftNode, None
        while p != rightNext:
            cur = p
            p = p.next
            cur.next = pre
            pre = cur
        
        # 4. 拼接
        leftPre.next = pre 
        # 是不是None，都不影响拼接
        leftNode.next = rightNext

        # 5. 重新指向head
        head = dumpy.next

        return head


# 头插法，自己写的
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        """
            还可以使用头插法，反转， 一次遍历求结果. 举个例子：
            1 -> 2 -> 3 -> 4 -> 5  从节点 2 到 4 反转。 p指针遍历每个元素， cur表示当前元素。 从 3， 4 依次头插法 1 后面， 最后 2.next = 5  就完成了
        """
        # 因为可能头结点也需要反转，统一逻辑，头插法设立 首元结点
        dumpy = ListNode(0, head)
        leftPre = dumpy
        # p 指针用于遍历链表所有节点, leftNode 用于记录 left索引对应节点
        p = leftNode = head
        index = 1
        # 遍历到 right位置就可以结束了
        while index <= right:
            # p 指针后移， cur 代表当前节点
            cur = p
            p = p.next
            
            if index == left - 1:
                leftPre = cur
                leftNode = cur.next
            elif index > left and index <= right:
                # 先取出当前节点
                cur.next = leftPre.next
                leftPre.next = cur

            index += 1

        leftNode.next = p

        return dumpy.next